1. Field of the Invention
The invention relates to cryptography, particularly a technique for: generating, for a given message to be signed, an authentic cryptographic signature that can be privately authenticated, by a recipient of the signed message, as having originated from a signor of the message; and appropriately authenticating such a signature.
2. Description of the Prior Art
Over the centuries, for as long as information has been communicated between two individuals, information has been susceptible to third-party interception, eavesdropping, compromise and/or corruption. Clearly, the problem of securely protecting information from such acts has existed for quite a long time.
Traditionally, this problem has been handled through the development, over the years, of increasingly sophisticated cryptographic techniques. One class of these techniques involves the use of key-based ciphers. In particular, through a key-based cipher, sequences of intelligible data, i.e., plaintext, that collectively form a message are each mathematically transformed, through an enciphering algorithm, into seemingly unintelligible data, i.e., so-called ciphertext. Not only must the transformation be completely reversible, i.e., two way in the sense that the ciphertext must be invertible back to its corresponding original plaintext but also on a 1:1 basis, i.e., each element of plaintext can only be transformed into one and only one element of ciphertext. In addition, a particular cipher that generated any given ciphertext must be sufficiently secure from cryptanalysis. To provide a requisite level of security, a unique key is selected which defines only one unique corresponding cipher, i.e., precluding, to the extent possible, a situation where multiple differing keys each yields reversible transformations between the same plaintext-ciphertext correspondence. The strength of any cryptographic technique and hence the degree of protection it affords from third-party intrusion is directly proportional to the time required, by a third-party, to perform cryptanalysis, e.g., with a key-based cipher to successfully convert the ciphertext into its corresponding plaintext without prior knowledge of the key. While no encryption technique is completely impervious from cryptanalysis, an immense number of calculations and an extremely long time interval required therefor--given the computing technology then available--required to break a cipher without prior knowledge of its key effectively renders many techniques, for all practical intents and purposes, sufficiently secure to warrant their widespread adoption and use. In that regard, as recently as a few years ago, if a cipher was of such complexity that it required on the order of man-years or more to break, in view of the state of the processing technology then available to do so, the underlying cryptographic technique was viewed by many as rendering a sufficient decree of security to warrant its use.
Public-key algorithms are one form of a key-based cipher. In such an algorithm, each communicating party generates a public-private key pair. Each party posts his(her) public key to a publicly accessible bulletin board, server or other facility, but maintains the corresponding private key in secret. In essence, an originating party desiring to encrypt a plaintext message and transmit it to another party, i.e., a destination party, both using the same public-key algorithm, will first access the public key of the destination party, encrypt the plaintext message using that public key into a ciphertext message and transmit the ciphertext message to the destination party. After receipt of the ciphertext message, the destination party, using his(her) private key, will then decrypt the message to recover the original plaintext. The keys are precisely computed, through use of very specific algorithms, to provide a requisite level of security while guaranteeing complete reversibility.
While public-key cryptographic systems can provide extremely secure encryption, to the point where breaking a public-key cipher is simply infeasible given the sheer number of operations potentially required to do so, such systems do have drawbacks that can limit their use. A principal drawback with a public-key system is its dependence on individual keys and a modulus that each carries a rather long bit sequence. For example, a modulus can easily be 1024 bits in length, while an individual key can be formed of a sequence of hundreds of bits. In some applications, such as cryptographic application programs where such keys can be readily stored, indexed and accessed as needed, the key length presents few, if any, practical problems for a user. For other applications, such long key sequences, even if converted to alphanumeric data, can still yield exceedingly long character strings that preclude easy manual entry by a user. In fact, the source of the extreme security of a public-key system lies in its use of very long bit sequences both for the keys and the modulus. If the modulus were to be appreciably shortened, then an encrypted message could be easily broken by cryptanalysis and hence the security of the underlying system readily compromised.
Computing technology continues to rapidly evolve. Processors, once unheard of just a few years ago in terms of their high levels of sophistication and speed, are becoming commercially available at ever decreasing prices. Consequently, processing systems, such as personal computers and workstations, that were previously viewed as not possessing sufficient processing power to break many so-called "secure" cryptographic ciphers are now, given their current power and sophistication, providing third parties with the necessary capability to effectively break those same ciphers. What may have taken years of continual computing a decade ago can now be accomplished in a very small fraction of that time. Hence, as technology evolves, the art of cryptography advances in lockstep in a continual effort to develop increasingly sophisticated cryptographic techniques that withstand correspondingly intensifying cryptanalysis.
Totally apart from cryptography, during at least the past decade, computer software manufacturers have been and continue to be subject to considerable unauthorized use of their products by unlicensed third parties. This is due, in part, to the relative ease with which a distribution media, such as diskettes or a CD-ROM, containing a software program can be duplicated. In an effort to thwart such unauthorized use, a relatively long alphanumeric indicia is often distributed with each legitimate copy of a packaged software product and must be entered by a user, when prompted during user installation of that copy on a computer. In particular, the copy includes an installation program which is first loaded and executed by the user to initiate and properly sequence through the entire installation process. Typically, at an early point in the installation process, the program will prompt the user of the copy being installed to manually enter the indicia. The indicia may contain, e.g., ten or more digits. In the case of distribution via compact discs (CDs), the indicia is printed on a label affixed to each case containing a CD. With diskette based distribution, the indicia is often printed on a certificate or other insert included within each software package. In any event, once the user has fully entered the indicia and has so signaled the program, typically by clicking an "OK" button (or the like) displayed on a monitor, the installation program will attempt to validate that indicia in an effort to determine whether the specific copy being installed is a licensed version or not. If the indicia is validated, the installation process proceeds; otherwise, it prematurely terminates. The underlying premise is that each user (i.e., licensee), who has legally obtained a valid copy, will possess the entire packaging as provided by the manufacturer and hence will have a valid indicia; but, an unauthorized user who simply obtains a copy of the program itself without any of the attendant packaging and/or inserts will not have the indicia. Given the length of the indicia, the probability is rather small that a user will simply pick a valid indicia at random. Hence, a user who attempts to install an unauthorized copy would be expected to repeatedly enter incorrect indicia, thus, for all practical purposes, never succeeding at installing the copy of program (s)he obtained and consequently rendering that copy effectively useless.
Unfortunately, in practice, the underlying algorithms for generating such indicia have proven to be relatively easy to discern and apparently have been rather widely and illicitly disseminated. Therefore, given the apparent availability of the algorithms, an unauthorized user, given some effort, can obtain a valid indicia for a program (s)he seeks to install. Hence, the manufacturer is often frustrated in its efforts to thwart use of such unauthorized copies.
Clearly, software manufacturers lose revenue from unauthorized copies of their products. Moreover, software manufacturers frequently provide customer support, of one form or another, for their products. In an effort to limit such support to their licensees, customer support staffs often require a user to first provide the indicia associated with his(her) copy of the product for which (s)he seeks support as a condition to receiving support. Given the ease with which unauthorized users can obtain valid indicia, software manufacturers are experiencing considerable difficulty in discriminating between licensees and such unauthorized users in order to provide support to the former while denying it to the latter. As a result, manufacturers often unwittingly provide support to unauthorized users, thus incurring additional and unnecessary support costs. If the number of unauthorized users of a given software product is sufficiently large, then these excess costs associated with that product can be quite significant.
Therefore, a need exists in the art for a technique that permits a software manufacturer to appreciably reduce the incidence of unauthorized copying of its software product. Such a technique should uniquely identify each copy of that product and permit the authenticity of that particular copy to be determined. Preferably, such a technique should involve cryptographically generating a sufficiently secure identifier through a public-key system (i.e., given the current state and expected evolution of computer technology, a third party, in the absence of knowing the keys, would face an infeasible task of generating a valid identifier). Furthermore, the identifier should be sufficiently long to ensure its security but not excessively long as to frustrate a user who has to manually provide the identifier when necessary, such as during an installation process or during the course of obtaining product support. Through use of such a technique, a software manufacturer should be able to appreciably reduce unauthorized use of its software product and the associated costs it otherwise incurs. Doing so might, in turn, economically permit that manufacturer to offer other services, such as promotions, to its licensees, thereby increasing licensee satisfaction with both the product and the manufacturer.